package com.c2b.algorithm.leetcode.base;

import java.util.*;

/**
 * <a href='https://leetcode.cn/problems/path-sum-ii/'>路径总和 II(Path Sum II)</a>
 * <p>给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。</p>
 * <p>叶子节点 是指没有子节点的节点。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 *      输出：[[5,4,11,2],[5,8,4,5]]
 *
 * 示例 2：
 *      输入：root = [1,2,3], targetSum = 5
 *      输出：[]
 *
 * 示例 3：
 *      输入：root = [1,2], targetSum = 0
 *      输出：[]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点总数在范围 [0, 5000] 内</li>
 *     <li>-1000 <= Node.val <= 1000</li>
 *     <li>-1000 <= targetSum <= 1000</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0112PathSum_I_S 路径总和 I(Path Sum I)
 * @see LC0113PathSum_II_M 路径总和 II(Path Sum II)
 * @see _LC0437PathSum_M_MMMMM 路径总和 III(Path Sum III)
 * @since 2023/5/11 14:14
 */
public class LC0113PathSum_II_M {

    static class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
            List<List<Integer>> allPathsList = new ArrayList<>();
            dfs(root, targetSum, new ArrayList<>(), allPathsList);
            return allPathsList;
        }

        private void dfs(TreeNode currNode, int targetSum, List<Integer> currPath, List<List<Integer>> allPathsList) {
            if (currNode == null) {
                return;
            }
            targetSum -= currNode.val;
            currPath.add(currNode.val);
            // 如果是叶子节点，并且路径和等于 targetSum，添加到结果中。并返回
            if (currNode.left == null && currNode.right == null && 0 == targetSum) {
                allPathsList.add(new ArrayList<>(currPath));
                return;
            }
            if (currNode.left != null) {
                dfs(currNode.left, targetSum, currPath, allPathsList);
                // 回溯
                currPath.remove(currPath.size() - 1);
            }
            if (currNode.right != null) {
                dfs(currNode.right, targetSum, currPath, allPathsList);
                // 回溯
                currPath.remove(currPath.size() - 1);
            }
        }

        public List<List<Integer>> pathSum2(TreeNode root, int targetSum) {
            List<List<Integer>> ans = new ArrayList<>();
            if (root == null) {
                return ans;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            Map<TreeNode, TreeNode> parentNodeMap = new HashMap<>();
            parentNodeMap.put(root, null);
            while (!queue.isEmpty()) {
                TreeNode currNode = queue.poll();
                // 到达叶子节点。向上找所有经过的节点，判断路径和是否等于 targetSum
                if (currNode.left == null && currNode.right == null) {
                    int difference = targetSum;
                    List<Integer> currPath = new ArrayList<>();
                    while (currNode != null) {
                        difference -= currNode.val;
                        currPath.add(0, currNode.val);
                        currNode = parentNodeMap.get(currNode);
                    }
                    if (difference == 0) {
                        ans.add(currPath);
                    }
                } else {
                    if (currNode.left != null) {
                        queue.offer(currNode.left);
                        parentNodeMap.put(currNode.left, currNode);
                    }
                    if (currNode.right != null) {
                        queue.offer(currNode.right);
                        parentNodeMap.put(currNode.right, currNode);
                    }
                }
            }
            return ans;
        }
    }




    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left.left = new TreeNode(5);
        root.right.left.right = new TreeNode(1);
        Solution solution = new Solution();
        TreeNode.printTreeNodeVal(solution.pathSum(root, 22));
    }
}
